1. Field of the Invention
The present invention generally relates to computer graphics, and more particularly, to the process of rendering three-dimensional objects.
2. Description of the Related Art
Visualization software has proven to be very useful in evaluating three-dimensional designs long before the physical realization of those designs. In addition, visualization software has shown its cost effectiveness by allowing engineering companies to find design problems early in the design cycle, thus saving them significant amounts of money. Unfortunately, the need to view more and more complex scenes has outpaced the ability of graphics hardware systems to display them at reasonable frame rates. As scene complexity grows, visualization software designers need to carefully use the rendering resource provided by graphic hardware pipelines.
A hardware pipeline wastes rendering bandwidth when it discards rendered triangle work. Rendering bandwidth waste can be decreased by not asking the pipeline to draw triangles that it will discard. Various software methods for reducing pipeline waste have evolved over time. Each technique reduces waste at a different point within the pipeline. As an example, software culling of objects falling outside the view frustum can significantly reduce discards in a pipeline""s clipping computation. Similarly, software culling of backfacing triangles can reduce discards in a pipeline""s lighting computation.
The z-buffer is the final part of the graphics pipeline that discards work. In essence, the z-buffer retains visible surfaces, and discards those not visible because they are behind another surface (i.e. occluded). As scene complexity increases, especially in walk-through and CAD environments, the number of occluded surfaces rises rapidly and as a result the number of surfaces that the z-buffer discards rises as well. A frame""s average depth complexity determines roughly how much work (and thus rendering bandwidth) the z-buffer discards. In a frame with a per-pixel depth complexity of d the pipeline""s effectiveness is 1/d. As depth complexity rises, the hardware pipeline thus becomes proportionally less and less effective.
Software occlusion culling has been proposed as an additional tool for improving rendering effectiveness. A visualization program which performs occlusion culling effectively increases the overall rendering bandwidth of the graphics hardware by not asking the hardware pipeline to draw occluded objects. Computing a scene""s visible objects is the complementary problem to that of occlusion culling. Rather than removing occluded objects from the set of objects in a scene or frustum-culled scene, a program instead computes which objects are visible and instructs the rendering hardware to draw just those. A simple visualization program can compute the set of visible objects and draw those objects from the current viewpoint, thus allowing the pipeline to focus on removing backfacing polygons and the z-buffer to remove any non-visible surfaces of those objects.
One technique for computing the visible object set uses ray casting. RealEyes [Sowizral, H. A., Zikan, K., Esposito, C., Janin, A., Mizell, D., xe2x80x9cRealEyes: A System for Visualizing Very Large Physical Structuresxe2x80x9d, SIGGRAPH ""94, Visual Proceedings, 1994, p. 228], a system that implemented the ray casting technique, was demonstrated in SIGGRAPH 1994""s BOOM room. At interactive rates, visitors could xe2x80x9cwalkxe2x80x9d around the interior of a Boeing 747 or explore the structures comprising Space Station Freedom""s lab module.
The intuition for the use of rays in determining visibility relies on the properties of light. The first object encountered along a ray is visible since it alone can reflect light into the viewer""s eye. Also, that object interposes itself between the viewer and all succeeding objects along the ray making them not visible. In the discrete world of computer graphics, it is difficult to propagate a continuum of rays. So a discrete subset of rays is invariably used. Of course, this implies that visible objects or segments of objects smaller than the resolution of the ray sample may be missed and not discovered. This is because rays guarantee correct determination of visible objects only up to the density of the ray samples.
Visible-object determination has its roots in visible-surface determination. Foley et al. [Foley, J., van Dam, A., Feiner, S. and Hughes, J. Computer Graphics: Principles and Practice, 2nd ed., Addison-Wesley, Chapter 15, pp. 649-718, 1996] classify visible-surface determination approaches into two broad groups: image-precision and object-precision algorithms. Image precision algorithms typically operate at the resolution of the display device and tend to have superior performance computationally. Object precision approaches operate in object space-usually performing object-to-object comparisons.
A prototypical image-precision visible-surface-determination algorithm casts rays from the viewpoint through the center of each display pixel to determine the nearest visible surface along each ray. The following references describe various applications of visible-surface ray casting (or ray tracing).
Appel [xe2x80x9cSome Techniques for Shading Machine Rendering of Solidsxe2x80x9d, SJCC""68, pp. 37-45, 1968] uses ray casting for shading.
Goldstein and Nagel [Mathematical Applications Group, Inc., xe2x80x9c3-D Simulated Graphics Offered by Service Bureau,xe2x80x9d Datamation, 13(1), February 1968, p. 69.; see also Goldstein, R. A. and Nagel, R., xe2x80x9c3-D Visual Simulationxe2x80x9d, Simulation, 16(1), pp. 25-31, 1971] use ray casting for boolean set operations.
Kay et al. [Kay, D. S. and Greenberg, D., xe2x80x9cTransparency for Computer Synthesized Images,xe2x80x9d SIGGRAPH""79, pp.158-164] and Whitted [xe2x80x9cAn Improved Illumination Model for Shaded Displayxe2x80x9d, CACM, 23(6), pp.343-349, 1980] use ray tracing for refraction and specular reflection computations.
Airey et al. [Airey, J. M., Rohlf, J. H. and Brooks, Jr. F. P., xe2x80x9cTowards Image Realism with Interactive Update Rates in Complex Virtual Building Environmentsxe2x80x9d, ACM SIGGRAPH Symposium on Interactive 3D Graphics, 24, 2(1990), pp. 41-50] uses ray casting for computing the portion of a model visible from a given cell.
Another approach to visible-surface determination relies on sending beams or cones into a database of surfaces [see Dadoun et al., xe2x80x9cHierarchical approachs to hidden surface intersection testingxe2x80x9d, Proceeedings of Graphics Interface ""82, Toronto, May 1982, 49-56; see also Dadoun et al., xe2x80x9cThe geometry of beam tracingxe2x80x9d, In Joseph O""Rourke, ed., Proceeedings of the Symposium on Computational Geometry, pp.55-61, ACM Press, New York, 1985]. Essentially, beams become a replacement for rays. The approach usually results in compact beams decomposing into a set of possibly non-connected cone(s) after interacting with an object.
A variety of spatial subdivision schemes have been used to impose a spatial structure on the objects in a scene. The following four references pertain to spatial subdivision schemes:
(a) Glassner, xe2x80x9cSpace subdivision for fast ray tracing,xe2x80x9d IEEE CGandA, 4(10):15-22, October 1984;
(b) Jevans et al., xe2x80x9cAdaptive voxel subdivision for ray tracing,xe2x80x9d Proceedings Graphics Interface ""89, 164-172, June 1989;
(c) Kaplan, M. xe2x80x9cThe use of spatial coherence in ray tracing,xe2x80x9d in Techniques for Computer Graphics . . . , Rogers, D. and Eamshaw, R. A. (eds), Springer-Verlag, N.Y., 1987; and
(d) Rubin, S. M. and Whitted, T. xe2x80x9cA 3-dimensional representation for fast rendering of complex scenes,xe2x80x9d Computer Graphics, 14(3):110-116, July 1980.
Kay et al. [Kay, T. L. and Kajiya, J. T., xe2x80x9cRay Tracing Complex Scenesxe2x80x9d, SIGGRAPH 1986, pp. 269-278,1986], concentrating on the computational aspect of ray casting, employed a hierarchy of spatial bounding volumes in conjunction with rays, to determine the visible objects along each ray. Of course, the spatial hierarchy needs to be precomputed. However, once in place, such a hierarchy facilitates a recursive computation for finding objects. If the environment is stationary, the same data-structure facilitates finding the visible object along any ray from any origin.
Teller et al. [Teller, S. and Sequin, C. H., xe2x80x9cVisibility Preprocessing for Interactive Walkthroughs,xe2x80x9d SIGGRAPH ""91, pp.61-69] use preprocessing to full advantage in visible-object computation by precomputing cell-to-cell visibility. Their approach is essentially an object precision approach and they report over 6 hours of preprocessing time to calculate 58 Mbytes of visibility information for a 250,000 polygon model on a 50 MIP machine [Teller, S. and Sequin. C. H., xe2x80x9cVisibility computations in polyhedral three-dimensional environments,xe2x80x9d U.C. Berkeley Report No. UCB/CSD 92/680, April 1992].
In a different approach to visibility computation, Greene et al. [Greene, N., Kass, M., and Miller, G., xe2x80x9cHierarchical z-Buffer Visibility,xe2x80x9d SIGGRAPH ""93, pp.231-238] use a variety of hierarchical data structures to help exploit the spatial structure inherent in object space (an octree of objects), the image structure inherent in pixels (a Z pyramid), and the temporal structure inherent in frame-by-frame rendering (a list of previously visible octree nodes). The Z-pyramid permits the rapid culling of large portions of the model by testing for visibility using a rapid scan conversion of the cubes in the octree.
As used herein, the term xe2x80x9coctreexe2x80x9d refers to a data structure derived from a hierarchical subdivision of a three-dimensional space based on octants. The three-dimensional space may be divided into octants based on three mutually perpendicular partitioning planes. Each octant may be further partitioned into eight sub-octants based on three more partitioning planes. Each sub-octant may be partitioned into eight sub-suboctants, and so forth. Each octant, sub-octant, etc., may be assigned a node in the data structure. For more information concerning octrees, see pages 550-555, 559-560 and 695-698 of Computer Graphics: principles and practice, James D. Foley et al., 2nd edition in C, ISBN 0-201-84840-6, T385.C5735, 1996.
The depth complexity of graphical environments continues to increase in response to consumer demand for realism and performance. Thus, the efficiency of an algorithm for visible object determination has a direct impact on the marketability of a visualization system. The computational bandwidth required by the visible object determination algorithm determines the class of processor required for the visualization system, and thereby affects overall system cost. Thus, improved systems and methods for performing visible object determination are greatly desired.
Furthermore, the visibile object set estimated by the visible object determination algorithm should be closely approximate the actual set of visible objects. If the algorithm significantly over-estimates the set of visible objects, computational bandwidth is wasted rendering objects that are not really visible. If the algorithm significantly under-estimates the set of visibile objects, the missing objects which should be present in the displayed image are not likely to go unnoticed by the user. Thus, there exists a significant need for a visibility determination system and method which more accurately estimates the set of visible objects with respect to current viewpoint.
The problems outlined above may at least in part be solved by a system and method that are configured to utilize ancillary geometry for object culling. A visibility algorithm (e.g., one using cones or rays) is applied to either individual bounding hulls or a hierarchy of bounding hulls. Once a particular ray or cone is determined to intersect the smallest bounding hull corresponding to a particular object, an additional comparison may be performed applying the same ray or cone to ancillary geometry associated with the object. Advantageously, the ancillary geometry may be configured to more closely approximate the object than the bounding hull.
In various embodiments, the methods described herein may be implemented as a software program on a programmable processor, in dedicated hardware, or in a combination of programmable hardware and dedicated hardware. The software program may be implemented as part of an application programming interface (API), as part of graphics application, a browser, or as part of a graphics system driver.
In one embodiment, the method for performing visibility culling includes receiving a scene graph having graphics data that describes a plurality of graphics objects (each object may comprise a plurality of graphics primitives such as polygons, subdivision surfaces, or NURBS). Next, bounding hulls for the graphics objects may be determined. These bounding hulls may in turn be combined (i.e. recursively grouped) to form a hierarchy of larger bounding hulls. A visibility frustum for the current viewpoint may be selected and compared with the larger bounding hulls. Next, ancillary geometry may be determined for one or more of the objects that have bounding hulls falling within the visibility frustum. Once the ancillary geometry data is determined, it may be stored to memory and linked to the scene graph via pointers.
In some implementations, the geometry data associated with a particular level of detail may be used as the ancillary geometry data. To avoid inordinate processing load, the level of detail chosen to define the ancillary geometry for a graphics object is typically lower than the highest level of detail available for the graphics object. However, the level of detail used for rendering the object is independent of the level of detail used for the ancillary geometry. For example, a high level of detail may be rendered, but a low level of detail may be used as the ancillary geometry for visibility determination. Once the ancillary geometry is selected or generated, it is then compared with one or more cones or rays within the visibility frustum that originate at the selected viewpoint. If the cones or rays intersect the ancillary geometry before intersecting any other object, then the corresponding object is selected (e.g., tagged) for rendering.
In some embodiments, the method may include detecting visible changes (e.g., deformations, translations, or rotations) in one or more of the objects, and then updating the ancillary geometry accordingly (e.g., updating at least the changed objects).
The ancillary geometry may be determined by selecting a particular set of geometry data from a group of different levels of detail for the corresponding object. Alternatively, the ancillary geometry data may be determined by using vertex decimation. In yet another embodiment, the ancillary geometry is pre-generated and accompanies the object""s geometry data. The ancillary geometry may also be determined by replacing a number Np of graphics primitives with a single graphics primitive that approximates the Np primitives. For example, a number of polygons creating a cylindrical shape may be replaced with a cylinder.
The method may be implemented as a computer program that is configured to receive information regarding a scene graph (including graphics data describing a plurality of graphics objects). As noted above, the software may be configured to compare a portion of a selected visibility frustum with a bounding hull corresponding to one or more of the graphics objects. If the portion of the selected visibility frustum intersects the bounding hull, then the portion of the selected visibility frustum is compared with ancillary geometry corresponding to the one or more graphics objects. If the portion of the selected visibility frustum intersects the ancillary geometry, then the corresponding graphics object or objects are identified for possible rendering. The ancillary geometry may preferably have more information than the bounding hull and less information than the graphics data corresponding to the object as a whole. As noted above, different techniques may be used to determine the ancillary geometry, including vertex decimation.